package com.chao.stucture.tree;

import java.util.Stack;

/**
 * @author : Rookie
 * @description : 二叉查找树
 * @date : 2023/7/12
 */
public class BinarySearchTree {

    /**
     * 根节点
     */
    private TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    public void insert(int val) {
        if(root == null) {
            root = insert(null,val);
        } else {
            insert(root,val);
        }
    }

    public TreeNode insert(TreeNode rootNode,int val) {
        if (rootNode == null) {
            rootNode = new TreeNode(val);
            return rootNode;
        }

        if (val > rootNode.element) {
            rootNode.right = insert(rootNode.right,val);
        } else if (val < rootNode.element) {
            rootNode.left = insert(rootNode.left,val);
        }
        return rootNode;
    }

    public TreeNode search(int val) {
        return search(root,val);
    }

    private TreeNode search(TreeNode treeNode,int val) {
        if (treeNode == null || treeNode.element == val) {
            return treeNode;
        }

        if (val > treeNode.element) {
            return search(treeNode.right,val);
        } else {
            return search(treeNode.left, val);
        }
    }

    public void delete(int val) {
        root = delete(root,val);
    }

    private TreeNode delete(TreeNode node,int val) {
        if (node == null) {
            return null;
        }

        if (val > node.element) {
            node.right = delete(node.right,val);
        } else if (val < node.element) {
            node.left =  delete(node.left,val);
        } else {
            // 是要删除的节点
            if (node.left == null && node.right == null) { // 该节点为叶子节点
                node = null;
            } else if (node.left == null) { // 该节点只有右子节点
                node = node.right;
            } else if (node.right == null) { // 该节点只有左子节点
                node = node.left;
            } else { // 该节点既有左子节点又有右子节点
                TreeNode successor = findMin(node.right); // 找到右子树中的最小节点
                node.element = successor.element; // 将该节点的值更新为右子树中最小节点的值
                node.right = delete(node.right, successor.element); // 在右子树中删除最小节点
            }
        }
        return node;
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    /**
     * 非递归前序遍历
     * @param root
     */
    private void preorderTraversal(TreeNode root) {
        System.out.println("前序遍历结果是：");
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            System.out.print(treeNode.element + " ");
            while (treeNode.right != null) {
                stack.push(treeNode.right);
            }
            while (treeNode.left != null) {
                stack.push(treeNode.left);
            }
        }
    }

    /**
     * 非递归中序遍历
     * @param root
     */
    private void inorderTraversal(TreeNode root) {
        System.out.println("中序遍历结果是：");
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            System.out.print(treeNode.element);
            while (treeNode.right != null) {
                stack.push(treeNode.right);
            }
            while (treeNode.left != null) {
                stack.push(treeNode.left);
            }
        }
    }

    /**
     * 非递归后序遍历
     * @param root
     */
    private void postorderTraversal(TreeNode root) {
        System.out.println("后序遍历结果是：");
        if (root == null) {
            return;
        }
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            System.out.print(treeNode.element);
            while (treeNode.right != null) {
                stack.push(treeNode.right);
            }
            while (treeNode.left != null) {
                stack.push(treeNode.left);
            }
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // 插入元素
        bst.insert(5);
        bst.insert(3);
        bst.insert(7);
        bst.insert(2);
        bst.insert(4);
        bst.insert(6);
        bst.insert(8);
//
//        // 查找元素
//        TreeNode node1 = bst.search(4);
//        System.out.println("查找结果：" + (node1 != null ? node1.element : "未找到"));
//
//        // 删除元素
//        bst.delete(4);
//        TreeNode node2 = bst.search(4);
//        System.out.println("查找结果：" + (node2 != null ? node2.element : "未找到"));
        bst.preorderTraversal(bst.root);
    }
}
